package org.laizili.solution.leetcode;

/**
 * <a href="https://leetcode.cn/problems/find-the-winner-of-the-circular-game/">1823. 找出游戏的获胜者</a>
 * <p>
 *     tags: 约瑟夫环; 循环链表模拟; 队列模拟; 数学计算
 */
public class Problem1823 {
    /*
     *  自定义循环链表
     */
    private static class Solution {
        private static class Node {
            int val;
            Node next;

            Node(int val, Node next) {
                this.val = val;
                this.next = next;
            }

            Node(int val) {
                this.val = val;
            }
        }

        private static class CircleList {
            Node starter;
            Node predecessor;
            int size;

            CircleList(Node starter, Node predecessor, int size) {
                this.starter = starter;
                this.predecessor = predecessor;
                this.size = size;
            }

            /**
             * 删除循环链表下一个结点
             *
             * @param predecessor 待删除结点的前驱结点
             */
            void removeSuccessor(Node predecessor) {
                predecessor.next = predecessor.next.next;
                --size;
            }

            /**
             * 创建循环链表
             *
             * @param n 结点个数
             * @return {@link CircleList}
             */
            private static CircleList of(int n) {
                // 循环链表
                Node head = new Node(1);
                head.next = head;
                Node tail = head;
                for (int i = 2; i <= n; i++) {
                    tail.next = new Node(i, tail.next);
                    tail = tail.next;
                }
                return new CircleList(head, tail, n);
            }
        }

        public int findTheWinner(int n, int k) {
            CircleList circleList = CircleList.of(n);
            while (circleList.starter.next != circleList.starter) {
                // starter is 1
                // move k-1 step
                int m = (k - 1) % circleList.size;
                for (int i = 1; i <= m; i++) {
                    circleList.predecessor = circleList.starter;
                    circleList.starter = circleList.starter.next;
                }
                circleList.starter = circleList.starter.next;
                circleList.removeSuccessor(circleList.predecessor);

            }
            return circleList.starter.val;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().findTheWinner(6, 5));
        System.out.println(new Solution().findTheWinner(1, 1));
        System.out.println(new Solution().findTheWinner(2, 1));
    }
}
